﻿#region LICENSE
/****************************************************************************
 *                                                                          *
 *  CoderBlu.Collections - Thread-safe Collections                          *
 *  Copyright (C) 2008 Rodger "Nullz" Aiken <nullz.void@gmail.com>          *
 *                                                                          *
 *  This library is free software; you can redistribute it and/or modify    *
 *  it under the terms of the GNU Library General Public License as         *
 *  published by the Free Software Foundation; either version 2 of the      *
 *  License, or (at your option) any later version.                         *
 *                                                                          *
 *  This library is distributed in the hope that it will be useful, but     *
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANT     *
 *  ABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library        *
 *  General Public License for more details.                                *
 *                                                                          *
 *  You should have received a copy of the GNU Library General Public       *
 *  License along with this library; if not, write to the Free Foundation,  *
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA        *
 *                                                                          *
 ****************************************************************************/
#endregion

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Security.Permissions;

namespace CoderBlu.Collections
{
	[Serializable]
	public class LinkedList<T> :
		SynchronizedCollection,
		ICollection, ICollection<T>,
		IEnumerable, IEnumerable<T>,
		ISerializable, IDeserializationCallback
	{
		public class Node
		{
			internal LinkedList<T> _list;
			internal Node _prev;
			internal Node _next;
			private T _value;

			public Node ( T value )
				: this(value, null, null, null) {
			}
			internal Node ( T value, Node prev, Node next, LinkedList<T> list ) {
				this._value = value;
				this._prev = prev;
				this._next = next;
				this._list = list;
			}

			public LinkedList<T> List {
				get { return this._list; }
			}

			public Node Next {
				get { return this._next; }
			}

			public Node Previous {
				get { return this._prev; }
			}

			public T Value {
				get { return this._value; }
				set { this._value = value; }
			}

			internal void Self ( LinkedList<T> list ) {
				this._list = list;
				this._next = this._prev = this;
			}

			internal void Insert ( LinkedList<T> list, Node prev, Node next ) {
				this._list = list;
				prev._next = this;
				next._prev = this;
				this._next = next;
				this._prev = prev;
			}

			internal void Remove ( ) {
				this._prev._next = this._next;
				this._next._prev = this._prev;
				this._next = this._prev = null;
				this._list = null;
			}
		}

		private SerializationInfo _info;
		private Node _first;
		private volatile int _count;

		public int Count {
			get { return this._count; }
		}

		public Node First {
			get {
				lock ( this._synclock )
					return this._first;
			}
		}

		public Node Last {
			get {
				lock ( this._synclock ) {
					if ( this._first != null )
						return this._first._prev;
				}

				return null;
			}
		}

		bool ICollection.IsSynchronized {
			get { return true; }
		}

		object ICollection.SyncRoot {
			get { return this; }
		}

		bool ICollection<T>.IsReadOnly {
			get { return false; }
		}

		public void AddAfter ( Node node, Node newNode ) {
			if ( node == null )
				throw new ArgumentNullException("node");

			if ( node._list != this )
				throw new ArgumentException("Node is a member of another tree", "node");

			if ( newNode == null )
				throw new ArgumentNullException("newNode");

			if ( newNode._list != null )
				throw new ArgumentException("Node is a member of another tree", "newNode");

			lock ( this._synclock ) {
				newNode.Insert(this, node, node._next);

				this._count++;
			}
		}
		public Node AddAfter ( Node node, T value ) {
			Node newNode = new Node(value);

			this.AddAfter(node, newNode);
			return newNode;
		}

		public void AddBefore ( Node node, Node newNode ) {
			if ( node == null )
				throw new ArgumentNullException("node");

			if ( node._list != this )
				throw new ArgumentException("Node is a member of another tree", "node");

			if ( newNode == null )
				throw new ArgumentNullException("newNode");

			if ( newNode._list != null )
				throw new ArgumentException("Node is a member of another tree", "newNode");

			lock ( this._synclock ) {
				newNode.Insert(this, node._prev, node);

				if ( node == this._first )
					this._first = newNode;

				this._count++;
			}
		}
		public Node AddBefore ( Node node, T value ) {
			Node newNode = new Node(value);

			this.AddBefore(node, newNode);
			return newNode;
		}

		public void AddFirst ( Node node ) {
			if ( node == null )
				throw new ArgumentNullException("node");

			if ( node._list != null )
				throw new ArgumentException("Node is a member of another tree", "node");

			lock ( this._synclock ) {
				if ( this._first != null ) {
					node.Insert(this, this._first._prev, this._first);
				} else {
					node.Self(this);
				}

				this._first = node;
				this._count++;
			}
		}
		public Node AddFirst ( T value ) {
			Node node = new Node(value);

			this.AddFirst(node);
			return node;
		}

		public void AddLast ( Node node ) {
			if ( node == null )
				throw new ArgumentNullException("node");

			if ( node._list != null )
				throw new ArgumentException("Node is a member of another tree", "node");

			lock ( this._synclock ) {
				if ( this._first != null ) {
					node.Insert(this, this._first._prev, this._first);
				} else {
					node.Self(this);

					this._first = node;
				}

				this._count++;
			}
		}
		public Node AddLast ( T value ) {
			Node node = new Node(value);

			this.AddLast(node);
			return node;
		}

		public void Clear ( ) {
			lock ( this._synclock ) {
				this._first = null;
				this._count = 0;
			}
		}

		public bool Contains ( T value ) {
			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					Node node = null;

					if ( ( node = this._first ) == null )
						return false;

					do {
						if ( value.Equals(node.Value) )
							return true;
					} while ( ( node = node.Next ) != this._first );
				}
			}

			return false;
		}

		public void CopyTo ( T [ ] array ) {
			this.CopyTo(array, 0);
		}
		public void CopyTo ( T [ ] array, int arrayIndex ) {
			if ( array == null )
				throw new ArgumentNullException("array");

			if ( ( arrayIndex < 0 ) || ( arrayIndex >= array.Length ) )
				throw new ArgumentOutOfRangeException("arrayIndex");

			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					Node node = null;

					if ( ( node = this._first ) != null ) {
						do {
							if ( arrayIndex >= array.Length )
								return;

							array [ arrayIndex++ ] = node.Value;
						} while ( ( node = node.Next ) != this._first );
					}
				}
			}
		}

		public Node Find ( T value ) {
			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					Node node = null;

					if ( ( node = this._first ) == null )
						return null;

					do {
						if ( value.Equals(node.Value) )
							return node;

						node = node.Next;
					} while ( node != this._first );
				}
			}

			return null;
		}

		public Node FindLast ( T value ) {
			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					Node node = null;

					if ( ( node = this._first ) == null )
						return null;

					do {
						node = node.Previous;

						if ( value.Equals(node.Value) )
							return node;
					} while ( node != this._first );
				}
			}

			return null;
		}

		public IEnumerator<T> GetEnumerator ( ) {
			lock ( this._synclock ) {
				Node node = null;

				if ( ( node = this._first ) == null )
					yield break;

				do {
					yield return node.Value;
				} while ( ( node = node.Next ) != this._first );
			}
		}

		[SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
		public virtual void GetObjectData ( SerializationInfo info, StreamingContext context ) {
			if ( info == null )
				throw new ArgumentNullException("info");

			lock ( this._synclock )
				info.AddValue("items", this.ToArray());
		}

		public virtual void OnDeserialization ( object sender ) {
			lock ( this._synclock ) {
				if ( this._info != null ) {
					T [ ] items = ( ( T [ ] ) this._info.GetValue("items", typeof(T [ ])) );

					for ( int i = 0 ; i < items.Length ; i++ )
						this.AddLast(items [ i ]);

					this._info = null;
				}
			}
		}

		public bool Remove ( T value ) {
			if ( this._count < 1 )
				return false;

			Node node = null;

			lock ( this._synclock ) {
				if ( ( node = this.Find(value) ) != null )
					this.Remove(node);
			}

			return ( node != null );
		}
		public void Remove ( Node node ) {
			if ( node == null )
				throw new ArgumentNullException("node");

			if ( node._list != this )
				throw new ArgumentException("Node is not a member of this tree", "node");

			lock ( this._synclock ) {
				if ( --this._count < 1 )
					this._first = null;

				if ( node == this._first )
					this._first = this._first._next;

				node.Remove();
			}
		}

		public void RemoveFirst ( ) {
			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					if ( this._first != null )
						this.Remove(this._first);
				}
			}
		}

		public void RemoveLast ( ) {
			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					if ( this._first != null )
						this.Remove(this._first._prev);
				}
			}
		}

		public T [ ] ToArray ( ) {
			lock ( this._synclock ) {
				T [ ] array = new T [ this._count ];

				this.CopyTo(array);
				return array;
			}
		}

		void ICollection.CopyTo ( Array array, int index ) {
			if ( array == null )
				throw new ArgumentNullException("array");

			if ( ( index < 0 ) || ( index >= array.Length ) )
				throw new ArgumentOutOfRangeException("index");

			if ( this._count > 0 ) {
				lock ( this._synclock ) {
					Node node = null;

					if ( ( node = this._first ) != null ) {
						do {
							if ( index >= array.Length )
								break;

							array.SetValue(node.Value, index++);
						} while ( ( node = node.Next ) != this._first );
					}
				}
			}
		}

		void ICollection<T>.Add ( T value ) {
			this.AddLast(value);
		}

		IEnumerator IEnumerable.GetEnumerator ( ) {
			return this.GetEnumerator();
		}
	}
}